package DataStructure.SortMethod;

import java.util.Arrays;

/**
 * @time: 2021/4/28/028 21:38
 * @author: Zhurunhe
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort1(arr);
        System.out.println(Arrays.toString(arr));


//        for (int i = 5; i <arr.length; i++) {
//            for (int j = i-5; j >=0; j-=5) {
//                System.out.println(arr[j]);
//            }
//        }
    }

    //交换法
    public static void shellSort(int[] arr) {
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //下面循环语句是用来循环已分完组的数组 比如5组  i=5 j=0 i从下标为5和j从下标为0开始配对 两个一组 共五组 然后比较大小交换
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }

        /*
        //10/2=5
        for (int i = 5; i <arr.length; i++) {
            for (int j = i-5; j >=0; j-=5) {
                if (arr[j]>arr[j+5]){
                    temp=arr[j];
                    arr[j]=arr[j+5];
                    arr[j+5]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        //5/2=2
        for (int i = 2; i <arr.length; i++) {
            for (int j = i-2; j >=0; j-=2) {
                if (arr[j]>arr[j+2]){
                    temp=arr[j];
                    arr[j]=arr[j+2];
                    arr[j+2]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        //2/2=1
        for (int i = 1; i <arr.length; i++) {
            for (int j = i-1; j >=0; j-=1) {
                if (arr[j]>arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));*/
    }

    //移位法
    public static void shellSort1(int[] arr) {
        //5 2 1组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //gap在这是表示从第几个开始 并且是每隔gap位进行对比交换 如2 就是隔一位进行对比交换 一直与前面对比 直达找到对应的位置
                int insertIndex = i;
                int insertValue = arr[insertIndex];
                if (arr[insertIndex] < arr[insertIndex - gap]) {
                    while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
                        //后移
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertValue;
                }
            }
        }
    }
}
